﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace Utility.DataStructure
{
	public class LinkedDictionary<TKey, TValue> : IDictionary<TKey, TValue>
	{
		public class LinkedDictionaryNode
		{
			public TKey key;
			public TValue value;
			public LinkedDictionaryNode prev;
			public LinkedDictionaryNode next;

			public LinkedDictionaryNode (TKey key, TValue value)
			{
				this.key = key;
				this.value = value;
			}
		}

		Dictionary<TKey, LinkedDictionaryNode> dict = new Dictionary<TKey, LinkedDictionaryNode> ();
		LinkedDictionaryNode first = new LinkedDictionaryNode (default (TKey), default (TValue));
		LinkedDictionaryNode last = new LinkedDictionaryNode (default (TKey), default (TValue));

		public ICollection<TKey> Keys
		{
			get
			{
				TKey[] keys = new TKey[dict.Count];
				var node = first.next;
				int i = 0;
				while (node != last)
				{
					keys[i] = node.key;
					node = node.next;
				}
				return keys;
			}
		}

		public ICollection<TValue> Values
		{
			get
			{
				TValue[] keys = new TValue[dict.Count];
				var node = first.next;
				int i = 0;
				while (node != last)
				{
					keys[i] = node.value;
					node = node.next;
				}
				return keys;
			}
		}

		public int Count
		{
			get
			{
				return dict.Count;
			}
		}

		public bool IsReadOnly
		{
			get
			{
				return false;
			}
		}

		public TValue this[TKey key]
		{
			get
			{
				if (key.Equals (null))
				{
					throw new System.ArgumentNullException ();
				}
				var node = dict[key];
				if (node == null)
				{
					throw new KeyNotFoundException ();
				}
				return node.value;
			}

			set
			{
				if (dict.ContainsKey (key))
				{
					dict[key].value = value;
				}
				else
				{
					Add (key, value);
				}
			}
		}

		public LinkedDictionary ()
		{
			first.next = last;
			last.prev = first;
		}

		public void Add (TKey key, TValue value)
		{
			if (dict.ContainsKey (key))
			{
				throw new System.ArgumentException ();
			}

			var node = new LinkedDictionaryNode (key, value);
			dict[key] = node;
			var prev = last.prev;
			node.prev = prev;
			node.next = last;
			prev.next = node;
			last.prev = node;
		}

		public bool ContainsKey (TKey key)
		{
			return dict.ContainsKey (key);
		}

		public bool Remove (TKey key)
		{
			if (dict.ContainsKey (key))
			{
				var node = dict[key];
				dict.Remove (key);
				var prev = node.prev;
				var next = node.next;
				node.prev = null;
				node.next = null;
				prev.next = next;
				next.prev = prev;
				return true;
			}
			return false;
		}

		public bool TryGetValue (TKey key, out TValue value)
		{
			if (dict.ContainsKey (key))
			{
				value = dict[key].value;
				return true;
			}
			else
			{
				value = default (TValue);
				return false;
			}
		}

		public void Clear ()
		{
			dict.Clear ();
			first.next = last;
			last.prev = first;
		}

		public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
		{
			var node = first.next;
			while (node != last)
			{
				var ret = node;
				node = node.next;
				yield return new KeyValuePair<TKey, TValue> (ret.key, ret.value);
			}
		}



		#region IDictionary
		void ICollection<KeyValuePair<TKey, TValue>>.Add (KeyValuePair<TKey, TValue> item)
		{
			Add (item.Key, item.Value);
		}

		bool ICollection<KeyValuePair<TKey, TValue>>.Contains (KeyValuePair<TKey, TValue> item)
		{
			if (dict.ContainsKey (item.Key))
			{
				if (dict[item.Key].value.Equals (item.Value))
				{
					return true;
				}
			}
			return false;
		}

		bool ICollection<KeyValuePair<TKey, TValue>>.Remove (KeyValuePair<TKey, TValue> item)
		{
			if (dict.ContainsKey (item.Key))
			{
				if (dict[item.Key].value.Equals (item.Value))
				{
					Remove (item.Key);
					return true;
				}
			}
			return false;
		}

		void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int arrayIndex)
		{
			var node = first;
			//move to the start index
			for (int i = 0; i < arrayIndex; i++)
			{
				node = node.next;
			}
			//start copy
			int index = 0;
			node = node.next;
			while (node != last)
			{
				array[index] = new KeyValuePair<TKey, TValue> (node.key, node.value);
				index++;
				node = node.next;
			}
		}

		IEnumerator IEnumerable.GetEnumerator ()
		{
			var node = first.next;
			{
				var ret = node;
				node = node.next;
				yield return new KeyValuePair<TKey, TValue> (ret.key, ret.value);
			}
		}
		#endregion
	}
}
